package main.剑指OfferⅠ;

public class Day19 {
    public static void main(String[] args) {
        System.out.println("剑指Offer64.求1+2+...+n");
        System.out.println("剑指Offer68-Ⅰ.二叉搜索树的最近公共祖先");
        System.out.println("剑指Offer68-Ⅱ.二叉树的最近公共祖先");
    }
}

class Offer64{
    public int sumNums(int n) {
        return (n*(n+1))/2;
    }
}

class Offer68_Ⅰ{
    public TreeNode process(TreeNode root, TreeNode p, TreeNode q){
        if (root.val==p.val||root.val==q.val) return root;//节点为祖先
        if ((p.val<root.val&&q.val> root.val)||(p.val> root.val&&q.val< root.val)) return root;//分列左右
        TreeNode result=null;
        if (p.val<root.val&&q.val<root.val) result=process(root.left,p,q);//左子树
        if (p.val>root.val&&q.val>root.val) result=process(root.right,p,q);//右子树
        return result;
    }
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        return process(root,p,q);
    }
}

class Offer68_Ⅱ{
    public class Info{
        public boolean isExistNode1;
        public boolean isExistNode2;
        public TreeNode commonFather;
        public Info(boolean isExistNode1, boolean isExistNode2, TreeNode commonFather){
            this.isExistNode1=isExistNode1;
            this.isExistNode2=isExistNode2;
            this.commonFather=commonFather;
        }
    }
    public Info process(TreeNode root, TreeNode p, TreeNode q){
        if (root==null) return new Info(false,false,null);
        Info left=process(root.left, p, q);//左子树信息
        Info right=process(root.right, p, q);//右子树信息
        if (left.commonFather!=null||right.commonFather!=null){//其中一个子树中已经存在公共祖先
            return left.commonFather==null ? right : left;//将存在公共祖先的子树信息返回
        }
        boolean node1=false,node2=false;
        TreeNode temp=null;
        if (root==p|| left.isExistNode1==true || right.isExistNode1==true) node1=true;//当其中一个子树中存在p或当前节点为p
        if (root==q|| left.isExistNode2==true || right.isExistNode2==true) node2=true;//当其中一个子树中存在q或当前节点为q
        if (node1&&node2){//当本节点即为公共祖先时
            temp=root;
        }
        return new Info(node1,node2,temp);
    }
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        return process(root,p,q).commonFather;
    }
}